//
// Description: 115. 不同的子序列
// Created by Loading on 2022/6/11.
//

#include <bits/stdc++.h>

using namespace std;

int numDistinct(string s, string t) {
    int n = s.size(), m = t.size();

    // dp[i][j] 表示 s 的前 i 个字符的子序列中，t 的前 j 个字符出现的次数
    /* 注意：虽然题目给出答案在 int 范围内，但中间状态转移过程会爆 int，使用 unsigned long long */
    unsigned long long dp[n + 1][m + 1];
    memset(dp, 0, sizeof dp);

    // 空串是任何子序列的子序列，且只有一个
    for (int i = 0; i < n; ++i) {
        dp[i][0] = 1;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // 如果不使用第 i 个字符，由 dp[i - 1][j] 转移
            dp[i][j] = dp[i - 1][j];
            // 如果使用第 i 个字符，前提是当前位置的两个字母要相同
            if (s[i - 1] == t[j - 1]) {
                // 字母相同，可以忽略这两个字母，直接累加 dp[i - 1][j - 1]
                dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }

    return (int) dp[n][m];
}

int main() {
    string s = "babgbag";
    string t = "bag";

    auto res = numDistinct(s, t);

    cout << res << endl;

    return 0;
}